A local area network (LAN) is a low-cost, high-performance medium capable of transmitting information at high transfer rates among stations located within a moderately sized geographic area. Information is usually transmitted in the form of messages over a physical medium, e.g. a cable, in a broadcast fashion. Stations coupled to the LAN are assigned unique addresses. Each message contains a source address of a transmitter station and a destination address of a receiver station. The message is captured by a station having an address that matches the destination address.
In addition to source and destination addresses, each message also includes a multibit protocol-type field. The protocol-type field contains a code identifying a higher-level protocol used in the message. This protocol identifies the type of message, the procedures for sending and receiving the message, and/or the way in which the message is to be interpreted. For example, a message may announce services offered by a station connected to the network and the protocol field may then indicate that it is a message of that type. The protocol-type field permits different protocols to coexist over a single transmission medium. A message announcing availability of a service will ordinarily be a multicast message. The multicast message is a message transmitted to every station connected to the network; each station then processes the message to determine whether it must respond.
A bridge is a device that connects two or more LANs so that a station on one LAN may communicate with a station on another. A collection of LANs interconnected by a bridge is called an extended LAN. The bridge receives and stores each message from a particular LAN and then determines whether the message is to be forwarded to another LAN. Thus, the bridge is a "store-and-forward" device that isolates traffic to those LANs to which the traffic is destined. This allows simultaneous traffic on the individual LANs and increases the utilization and throughput of the extended LAN.
Operationally, the bridge typically maintains an address table for each interface or port to a LAN, i.e. a table for each LAN to which the bridge is connected. The address table contains the addresses of all stations connected to the particular LAN. A message received on one LAN by the bridge is "filtered", i.e. either forwarded to another LAN or discarded, on the basis of its destination address. More specifically, the address is filtered according to whether there is a match between the destination address of the message and an address stored in an address table and, if so, the table in which the match appears.
The bridge also typically maintains a separate protocol-type table containing a list of the higher-level protocols accomodated by the respective stations connected to the extended LAN. As each message is received by the bridge, an independent determination is made whether to forward the message based on the protocol-type. That is, the protocol-type field of the message is compared against the protocol-type entries in the table. If there is a match, the message is either forwarded or discarded, depending upon the configuration of the bridge.
The forwarding determination is typically made by a processor in the bridge using a hashing function. Hashing is an efficient means of finding entries in a table, as compared to searching each entry. Generally, an algorithm applied to the protocol-type field produces an index. The index identifies the location of an entry in the table. The content of the entry is then compared to the protocol-type of the message.
This forwarding decision, also referred to as "protocol filtering" is multi-directional; if the protocol-type is found in the table, the message is either forwarded to every LAN connected to the bridge or completely discarded. If forwarded, the message may require some stations to perform unnecessary computations in order to process a request to which they will not respond. If the message is discarded, the transmitting station might not receive the response it seeks. This results in the inefficient use of system resources.